package com.zzy.study.arithmetic;

public class Sort {

	public static void main(String[] args) {

		int[] data = { 5, 2, 1, 6, 3, 4, 9, 8, 7};
//		int[] data = { 1, 2, 4 , 3, 5 };
//		 print(bubbleSort(data));
//		 print(selectSort(data));
		// print(insertSort(data));
		print(shellSort(data));
//		print(quickSort(data, 0, data.length-1));
		
	}

	private static void print(int[] bubbleSort) {
		for (int i : bubbleSort) {
			System.out.println(i);
		}
		System.out.println("========");
	}

	/**
	 * 冒泡排序 时间复杂度O(n*n)，比较了n*(n-1)/2次，交换了n*n次
	 * i<data.length-1即可，data[0]到data[data.length-2]都会与data[data.length-1]比较。
	 * 
	 * @param data
	 * @return
	 */
//	public static int[] bubbleSort(int[] data) {
//		int temp = 0;
//		for (int i = 0; i < data.length - 1; i++) {
//			for (int j = i + 1; j < data.length; j++) {
//				if (data[i] > data[j]) {
//					temp = data[i];
//					data[i] = data[j];
//					data[j] = temp;
//				}
//			}
//		}
//		return data;
//	}
	
	public static int[] bubbleSort(int[] data) {
		int temp = 0;
		for(int i=0; i < data.length -1; i++) { //每一轮
			boolean exchange = false; //每一轮设置一个是否有元素交换的标志
			int j = data.length -1;
			for(; j > i; j--) {
				if(data[j] < data[j-1]) {     //元素和上一个元素比较
					temp = data[j];
					data[j] = data[j-1];
					data[j-1] = temp;
					exchange = true;        //有元素交换
				}
			}
			if(!exchange) {      //如果一轮下来，没有元素交换，说明data已经是排好序了，无需进行下一轮
				break;
			}
		}
		return data;
	}

	/**
	 * 直接选择排序 时间复杂度O(n*n)，比较了n*(n-1)/2次，交换了n次
	 * i<data.length-1即可，data[0]到data[data.length-2]都会与data[data.length-1]比较。
	 * 
	 * @param data
	 * @return
	 */
	public static int[] selectSort(int[] data) {
		int temp = 0;
		int position = 0;
		int j = 0;
		for (int i = 0; i < data.length - 1; i++) {			//i当前位置
			position = i;									//position最小下标
			j = i + 1;										
			for (; j < data.length; j++) {					//j从此区间选取最小下标
				if (data[j] < data[position]) {
					position = j;
				}
			}
			if (position != i) {	
				temp = data[i];
				data[i] = data[position];
				data[position] = temp;
			}
		}
		return data;
	}

	/**
	 * 直接插入排序 时间复杂度O(n*n)，比较了n*(n-1)/2次，复制了n*(n-1)/2次 i从1到data.length-1
	 * 
	 * @param data
	 * @return
	 */
	public static int[] insertSort(int[] data) {
		int temp = 0;
		for (int i = 1; i < data.length; i++) {
			if (data[i - 1] > data[i]) {
				temp = data[i];
				int j = i - 1;
				for (; j >= 0 && data[j] > temp; j--) {
					data[j + 1] = data[j]; // 复制
				}
				data[j + 1] = temp;
			}
		}
		return data;
	}

	// http://wb1991wb.iteye.com/blog/1704383
	// http://www.cnblogs.com/avril/archive/2011/05/04/2036467.html
	/**
	 * 希尔排序
	 */
	public static int[] shellSort(int[] data) {
		int increment = data.length; // 区间为increment
		int temp = 0;
		while (true) {
			increment = increment / 2;
			// 分成了几组，一组一组处理
			for (int x = 0; x < increment; x++) {
				// 下面就是直接插入排序，只是区间由1变成了increment
				for (int i = x + increment; i < data.length; i += increment) {
					if (data[i - increment] > data[i]) {
						temp = data[i];
						int j = i - increment;
						for (; j >= 0 && data[j] > temp; j -= increment) {
							data[j + increment] = data[j];
						}
						data[j + increment] = temp;
					}
				}
			}
			if (increment == 1) {
				break;
			}
		}
		return data;
	}

	/**
	 * 快速排序
	 * @param data
	 * @param low data最小下标
	 * @param high data最大下标
	 * @return
	 */
	public static int[] quickSort(int[] data, int low, int high) {
		// 对data[low..high]快速排序
		int pivotpos; // 划分后的基准记录的位置
		if (low < high) {// 仅当区间长度大于1时才须排序
			pivotpos = partition(data, low, high); // 对data[low..high]做划分
			quickSort(data, low, pivotpos - 1); // 对左区间递归排序
			quickSort(data, pivotpos + 1, high);// 对右区间递归排序
		}
		return data;
	}

	/**
	 * 划分算法，划分后
	 * 左边子区间中所有记录的关键字均小于等于基准记录pivot
	 * 右边的子区间中所有记录的关键字均大于等于pivot
	 * 基准记录pivot则位于正确的位置上
	 * @param data
	 * @param i
	 * @param j
	 * @return
	 */
	public static int partition(int[] data, int i, int j) {
		// 并返回基准记录的位置
		int pivot = data[i]; // 用区间的第1个记录作为基准 ，
		while (i < j) { // 从区间两端交替向中间扫描，直至i=j为止
			while (i < j && data[j] >= pivot) {
				// pivot相当于在位置i上
				j--; // 从右向左扫描，查找第1个关键字小于pivot的记录data[j]
			}
			if (i < j) // 表示找到的data[j]的关键字<pivot
				data[i++] = data[j]; // 相当于交换data[i]和data[j]，交换后i指针加1

			while (i < j && data[i] <= pivot) {
				// pivot相当于在位置j上
				i++; // 从左向右扫描，查找第1个关键字大于pivot的记录data[i]
			}
			if (i < j) // 表示找到了R[i]，使data[i]>pivot
				data[j--] = data[i]; // 相当于交换data[i]和data[j]，交换后j指针减1
		} // endwhile
		data[i] = pivot; // 基准记录已被最后定位
		return i;
	}

}
